//最小栈
/*设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

-231 <= val <= 231 - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 104 次
*/
class MinStack {
public:
    MinStack() {}

    void push(int val) {

        if (ministack.size() == 0 || ministack.top() >= val) {
            ministack.push(val);
        }
        nums.push_back(val);
    }

    void pop() {

        if (ministack.size() && ministack.top() == nums[nums.size() - 1]) {
            ministack.pop();
        }
        nums.pop_back();
    }

    int top() { return nums[nums.size() - 1]; }

    int getMin() { return ministack.top(); }

private:
    vector<int> nums;
    stack<int> ministack;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

 //丢失的数字
 /*给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
 -231 <= val <= 231 - 1
*/
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        bool* hash = new bool[nums.size() + 1](false);
        for (int i = 0; i < nums.size(); i++) {
            hash[nums[i]] = true;
        }
        for (int i = 0; i <= nums.size(); i++) {
            if (hash[i] == false)
                return i;
        }
        return -1;
    }
};
